#include <iostream>
#include <vector>
using namespace std;

/***
 * 给定不同面值的硬币 coins[] 和一个总金额 amount，求出能组成该金额的所有不同组合数。每种硬币可以使用无限次。
 * 
 * 
int coins[] = {1, 2, 5};
int amount = 5;
输出
组合总数：4
解释：

5 = 5
5 = 2 + 2 + 1
5 = 2 + 1 + 1 + 1
5 = 1 + 1 + 1 + 1 + 1

状态定义
dp[i] 表示组成金额 i 的组合总数
初始条件
dp[0] = 1（金额为0只有一种方式：不选任何硬币）
状态转移方程
cpp
for (int coin : coins) {
    for (int j = coin; j <= amount; ++j) {
        dp[j] += dp[j - coin];
    }
}
 * 
 */
int change(int amount, vector<int>& coins) {
    vector<int> dp(amount + 1, 0);
    dp[0] = 1;

    for (int i = 0; i < coins.size(); i++) {
        int coin = coins[i];
        for (int j = coin; j <= amount; ++j) {
            dp[j] += dp[j - coin];
        }
    }

    return dp[amount];
}

int main() {
    vector<int> coins = {1, 2, 5};
    int amount = 5;
    cout << "组合总数: " << change(amount, coins) << endl;
    return 0;
}